package com.linchong.dynamicprogramming.medium;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-20 18:58
 * @Description: CopyBooks$437-Copy Books-lintCode437
 */
public class CopyBooks {
	/**
	 * 有N本书需要被抄写，第i本书有A[i]页，i=0,1,...,N-1
	 * 有K个抄写员，每个抄写员可以抄写连续若干本书（如,第3~5本书，或者第10本书）
	 * 每个抄写员抄写速度都一样：一分钟一页
	 * 最少需要多少时间抄完所有的书？
	 *
	 * 例：
	 *  输入：
	 *      -A=[3,2,4],K=2
	 *  输出：
	 *      -5（第一个抄写员抄第一本书和第二本书，第二个抄写员抄写第三本书）
	 *
	 * step 1:确定状态
	 *      最后一步：最优策略中最后一个抄写员Bob（假设他是第K个）抄写的部分
	 *              一段连续的书，包括最后一本
	 *              如果blob抄写第j本到第N-1本，则Blob需要时间A[j]+,...,+A[N-1]
	 *              需要知道前面K-1个人最少需要多少时间抄完前j本书（第0~j-1本书）
	 *     子问题：
	 *          求k个人最短需要多少时间 -> 需要知道K-1个人最少需要多少时间抄完前j本书
	 *
	 *     状态：设f[k][i]为k个抄写员最少需要多长时间抄完前i本书，（因为需要控制抄写员个数）
	 *
	 * step 2:转移方程：
	 *          设f[k][i]为k个抄写员最少需要多长时间抄完前i本书，
	 *          //                          前面k-1个人抄j本书  第k个人抄第j到i-1本书
	 *          f[k][i] = min(j=0,...,i){max{f[k-1][j],A[j]+...+A[i-1]}}
	 *   k个抄写员最少需要多少时间抄完前i本书   k-1个抄写员最少需要多少时间抄完前j本书        第k个抄写员抄完第j至第i-1本书的时间
	 *   j=0:前k-1最少抄写0本书，j=i:第k个不抄书，每个人可以抄写0,1,2...书
	 *   max{f[k-1][j],A[j]+...+A[i-1]}：在最后一个人抄写j~(i-1)的情况下最多花的时间
	 *
	 * step 3:初始条件和转移方程
	 *  设f[k][i]为k个抄写员最少需要多少时间抄完前i本书
	 *  f[k][i] = min(j=0,1,...,i){max{f[k-1][j],A[j]+...+A[i-1]}}
	 *
	 *  初始条件：
	 *  -0个抄写员只能抄0本书
	 *      f[0][0] = 0,f[0][1]=f[0][2]=...=f[0][N] = 正无穷
	 *  -k个抄写员(k>0)需要0时间抄完0本书
	 *      f[k][0] = 0（k>0）
	 *
	 * step 4:计算顺序
	 *  计算f[0][0],f[0][1],...,f[0]N]
	 *  计算f[1][0],f[1][1],...,f[1]N]
	 *  ...
	 *
	 *  计算f[K][0],f[K][1],...,f[K]N]
	 *
	 *  结果 f[K][N]
	 *
	 *  时间复杂度O(N^2K),状态是K*N,每次要枚举最后一个人要抄写多少本书N
	 *  空间复杂度O(NK),优化后可达到O(N),f[k]和f[k-1]有关系，只需要开一个滚动数组即可
	 *
	 *  如果K>N,可以赋值K=N
	 *
	 */
	public int copyBooks(int[] A,int K){

		int n = A.length;
		if(n==0){
			return 0;
		}

		if(K>n){
			K = n;
		}

		int[][] f = new int[K+1][n+1];
		int i,j,k;


		// 0个人抄0本书
		f[0][0] = 0;
		// init，初始化0个人抄写1本书，2本书，...，n本书
		for (j  = 0; j <= n ; j++) {
			f[0][j] = Integer.MAX_VALUE;
		}


		int sum;
		// 前1个人，2个人,...,K个人
		for (k = 1; k <= K; k++) {
			// k copiers 0 books,takes 0 time
			// 第k个人抄0本书，花费时间0
			f[k][0] = 0;
			for (i = 1;i<=n;i++){
				//j从0枚举到i,计算A[j]到A[i-1],A[0]到A[i-1],A[1]到A[i-1],...,重复了多次，麻烦
				// 倒过来，j从i向回走，A[i-1],A[i-1]+A[i-2],...不断的加上，sum即出来了
				// f[k][i] = minj=0,...,i{max{f[k-1][j],A[j]+...+A[i-1]}}
				f[k][i] = Integer.MAX_VALUE;
				sum = 0;
				// 第k个人从书j开始，抄写到i-1,不用每次都求一遍和，第一次A[i-1],第二次A[i-1]+A[i-2]...
				// k=i,第k个抄写员抄写0本书
				for(j=i;j>=0;--j){
					f[k][i] = Math.min(f[k][i],Math.max(f[k-1][j],sum));
					if(j>0){
						sum+=A[j-1];
					}

				}

			}

		}
		return f[K][n];
	}
	public static void main(String[] args) {

	}
}
